from algo.data_structure import LinkedQueue

class Tree:
    """Abstract base cass representing a tree structure"""

    class Position:
        """An abstract position class"""
        def element(self):
            """Return the element stored at this position"""
            raise NotImplemented("must be inplemented by subclass")

        def __eq__(self, other):
            """Return true if other position represents the same location"""
            raise NotImplemented("must be implemented by subclass")

        def __ne__(self, other):
            """Return true if other does not represent the same lcoation"""
            raise NotImplemented("must be implemented by subclass")

    def root(self):
        """Return position at the tree's root"""
        raise NotImplemented("must be implemented by subclass")

    def parent(self, p):
        """Return position representing p's parent"""
        raise NotImplemented("must be implemented by subclass")

    def children(self, p):
        """Generate an iteration of position respresenting p's children"""
        raise NotImplemented("must be implemented by subclass")

    def left(self, p):
        """"Return a Position representing p's left child"""
        raise NotImplemented("must be implemented by subclass")

    def right(self, p):
        """Return a Postion representing p's right child"""
        raise NotImplemented("must be implemented by subclass")

    def num_children(self, p):
        """Return the number of children that position p has"""
        raise NotImplemented("must be implemented by subclass")

    def __len__(self):
        """Return the total number of elements in the tree"""
        raise NotImplemented("must be implemented by subclass")

    def is_root(self, p):
        """Return true if position p represents the root of the tree"""
        return self.root() == p

    def is_leaf(self, p):
        """Return true if position p does not have any children"""
        return self.num_children(p)

    def is_empty(self):
        """Return true if the tree is empty"""
        return len(self) == 0

    def depth(self, p):
        """Return the number of levels separating position p from the root"""
        if self.is_leaf(p):
            return 0
        else:
            return 1 + self.depth(self.parent(p))

    def _height(self, p):
        """Return the height of the subtree rooted at position p"""
        if self.is_leaf(p):
            return 0
        else:
            return 1 + max(self._height(c) for c in self.children(p))

    def height(self, p):
        """Return the height of the subtree rooted at position p"""
        if p is None:
            p = self.root()
        return self._height(p)

    def __iter__(self):
        """Generate an itreation of the tree's positions"""
        for p in self.positions():
            yield p.element()

    def positions(self):
        """Generate a n iteration of the tree's positions"""
        return self.preorder()

    def preorder(self):
        """Generate a preorder iteration of positions in the tree"""
        if not self.is_empty():
            for p in self._subtree_preorder(self.root()):
                yield p

    def _subtree_preorder(self, p):
        yield p  # 先遍历该节点
        for c in self.children(p):  # 递归遍历左右child
            for other in self._subtree_preorder(c):
                yield other

    def postorder(self):
        """Generate a postorder iteration of positions in the tree"""
        if not self.is_empty():
            for p in self._subtree_postorder(self.root()):
                yield p

    def _subtree_postorder(self, p):
        for c in self.children(p):  # 递归遍历左右child
            for other in self._subtree_postorder(other):
                yield other
        yield p  # 最后遍历该节点

    def inorder(self):
        """Generate a inorder iteration of positions in the tree"""
        if not self.is_empty():
            for p in self._subtree_inorder(self.root()):
                yield p

    def _subtree_inorder(self, p):
        if self.left(p) is not None:  # 先遍历左子树
            for other in self._subtree_inorder(self.left(p)):
                yield other
        yield p  # 遍历该节点

        if self.right(p) is not None:  # 先遍历右子树
            for other in self._subtree_inorder(self.right(p)):
                yield other

    def breadth_first(self):
        """
        Generate a breadth-first iteration of the positions of the tree
        广度优先遍历
        :return:
        """
        if not self.is_empty():
            fq = LinkedQueue()
            fq.enqueue(self.root())

            while not fq.is_empty():
                p = fq.dequeue()
                yield p
                for c in self.children(p):
                    fq.enqueue(c)
